package br.ufrj.dcc.org2.brent;

public class HashTable {
	private DataItem[] hashArray; // array de data items
	private int arraySize;
	private DataItem nonItem; // para itens apagados

	public HashTable(int size) // construtor
	{
		arraySize = size;
		hashArray = new DataItem[arraySize];
		nonItem = new DataItem(-1); // chave do item deletado eh -1
	}

	public void displayTable() {
		System.out.print("Tabela: ");
		for (int j = 0; j < arraySize; j++) {
			if (hashArray[j] != null)
				System.out.print(hashArray[j].getKey() + " ");
			else
				System.out.print("** ");
		}
		System.out.println("");
	}

	public int hashFunc(int key) {
		return key % arraySize; // funcao de hash 
	}

	public int hashFuncAuxi(int key) {
		return (key/arraySize) % arraySize; // funcao de hash que determina a proxima celula se a anterior estiver ocupada 
	}

	// TODO: Quando a tabela esta cheia, o loop do while se torna infinito! Arrumar isso... 
	public void insert(DataItem item) // insere um item
	// (assume q a tabela nao esta lotada)
	{
		boolean inseri = false;//serve de apoio para troca
		int jcounter = 1;//contador de avalia��es do item
		int icounter = 1;//contador de avalia��es do candidato a troca
		int key = item.getKey(); // extrai chave
		int hashVal = hashFunc(key); // hasheia a chave
		int scounter = calculaSConter(key, hashVal);//parametro de teste para troca
		DataItem item2;//item candidato a troca
		int hashVal2 = 0;    //termos referentes
		int key2 = 0;        //ao candidato a troca
		
		while(icounter + jcounter < scounter){
			if(hashArray[hashVal] == null){
				break;
			}
			item2 = hashArray[hashVal];
			key2 = hashArray[hashVal].getKey();
			hashVal2 = hashVal;
			// ate achar espaco vazio ou item coalescido (marcado com -1),
			while (true) {
				if(hashArray[hashVal] == null){ //evita testar a chave em item n�o inicializado
					break;
				}
				else if(hashArray[hashVal].getKey() != -1){
					break;
				}
				hashVal2 += hashFuncAuxi(key2); // vai para a proxima celula
				hashVal2 %= arraySize; // volta caso precise
				jcounter++;
			}
			if(icounter + jcounter < scounter){//melhor trocar
				hashArray[hashVal2] = item2; // insere item2
				hashArray[hashVal].setKey(key);
				inseri = true;
				break;
			}
			hashVal += hashFuncAuxi(key); // vai para a proxima celula
			hashVal %= arraySize; // volta caso precise
			icounter++;
		}
		if(inseri == false){//caso � haja troca busca posi��o
			while(true){
				if(hashArray[hashVal] == null){ //evita testar a chave em item n�o inicializado
					break;
				}
				else if(hashArray[hashVal].getKey() == -1){
					break;
				}
				hashVal += hashFuncAuxi(key); // vai para a proxima celula
				hashVal %= arraySize; // volta caso precise
			}
			hashArray[hashVal] = item;
		}
	}
	
	public int calculaSConter(int key, int hashVal){//parametro para troca de posi��es
		int scounter = 2;
		while (true) {
			if(hashArray[hashVal] == null){ //evita testar a chave em item n�o inicializado
				break;
			}
			else if(hashArray[hashVal].getKey() != -1){
				break;
			}
			hashVal += hashFuncAuxi(key); // vai para a proxima celula
			hashVal %= arraySize; // volta caso precise
			scounter++;
		}
		return scounter;
	}
	
	public boolean isFull(){//testa se a tabela esta cheia
		boolean full = true;
		
		for(int i=0;i<arraySize;i++){
			if(hashArray[i] == null){
				full = false;
				break;
			}
			else if(hashArray[i].getKey() != -1){
				full = false;
				break;
			}
		}
		return full;
	}
	
	public DataItem delete(int key) // deleta um DataItem
	{
		int hashVal = hashFunc(key); // hasheia a chave

		while (hashArray[hashVal] != null) // ate achar uma celula vazia,
		{ // achou a chave?
			if (hashArray[hashVal].getKey() == key) {
				DataItem temp = hashArray[hashVal]; // salva item
				hashArray[hashVal] = nonItem; // deleta item
				return temp; // retorna o item
			}
			++hashVal; // vai pra proxima celula
			hashVal %= arraySize; // volta pro comeco caso precise
		}
		return null; // nao achou o item :(
	} 

	public DataItem find(int key) // acha o item dando uma key
	{
		int hashVal = hashFunc(key); // hasheia a chave
		int hashInit = hashVal;

		while (hashArray[hashVal] != null) // ata achar celula vazia,
		{ // achou a chave?
			if (hashArray[hashVal].getKey() == key)
				return hashArray[hashVal]; // Sim! retorna o cara
			hashVal = hashFuncAuxi(key)+ hashVal; // vai pra proxima celula
			hashVal %= arraySize; // volta tudo caso precise
			if (hashVal == hashInit) break;
		}
		return null; // nao achou o cara :(
	}
}